/*
 * Copyright (c) 2005, The haXe Project Contributors
 * All rights reserved.
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   - Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *   - Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE HAXE PROJECT CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE HAXE PROJECT CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 */

/**
	The utility Sugar classes provide additional Iterable manipulation routines
**/


/**
	The BTree class adds a B-tree indexing scheme for arbitrary objects.
**/

/*package org.sugar.utilities;*/
import haxe.FastList;

class BTree<A>{
	private var order:Int;
	private var transform: A -> Float;
	private var root:BCell<A>;	
	public function new(?it:Iterable<A>, ?transform : A -> Float, ?order:Int = 3){
		this.order = order;
		if (order < 3){throw("Order must be higher than 3");}
		this.transform = transform;
		if (this.transform == null){this.transform = function (x:A) {return cast(x, Float);}}

		if (it != null){
			for ( i in it ){
				this.insert(i);
			}
		}	
	}
	
	public function getOrder(target_cell:BCell<A>):Int{
		var tc = target_cell;
		if (tc == null){return 0;}
		else if (tc.parent == null){tc = root;}
		else {tc = tc.parent.branch;}
		var count:Int = 1;
		while (tc.next != null){
			count++;
			tc = tc.next;
		}
		return count;
	}
	
	
	public function insert(item:A){
		var key = transform(item);
		var cell = new BCell<A>(key,item);
		insertCell(cell);
	}
	
	public function insertCell(cell:BCell<A>,?target_cell:BCell<A>){	
		var tc = target_cell;
		if (tc == null){tc = search(cell.matches.first());}
		if (tc == null){
			root = cell;
/*			trace('new root: '+ root.key);*/
		}
		else if (tc.key == cell.key){
			tc.matches.add(cell.matches.first());
/*			trace('added a match: '+cell.key);*/
		}
		else if (cell.key < tc.key){
			cell.next = tc.branch;
			cell.parent = tc;
			tc.branch = cell;
/*			trace('branched' + tc.key + ' with ' +cell.key);*/
		}
		else { // cell.key > target_cell.key
			cell.next = tc.next;
			cell.parent = tc.parent;
			tc.next = cell;
/*			trace('added ' + cell.key + ' after ' +tc.key);*/
		}
		
		
		if (getOrder(tc) > order){
			if (tc.parent == null){tc = root;}
			else {tc = tc.parent.branch;}
			split(tc);
			trace(root);
		}
	}
			
		
	

	
	
	/* Returns the BCell that matches the item, or the highest key value that is less than the item key value */
	public function search(item:A):BCell<A>{
		var search_key = transform(item);
		var current = root;
		while (current != null){
			if (search_key == current.key){return current;}
			if (search_key > current.key){
				if (current.next == null){ return current; } // insert at the end of a node chain
				else if (search_key < current.next.key && current.next.branch == null){return current;} // insert inbetween two nodes
			} 
			else if (search_key < current.key){
				if (current.branch == null){return null;} // insert at root
				else { current = current.branch; continue;}
			}	
			current = current.next;
		}
		return current;
	}
	
	public function findMatches(item:A):List<A>{
		var target_cell = search(item);
		if (target_cell == null){return null;}
		
	}
	
	public function split(target_cell:BCell<A>){
		var split_on_count:Int = Math.floor(order/2);
		var count:Int = 1;
		var cell1 = target_cell;
		while (count < split_on_count){
			cell1 = cell1.next;
			count++;
		}

		var cell2 = cell1.next; // cell 2 is the median
		var cell3 = cell2.next; // cell 3 is the leftovers
		cell1.next = null; cell2.next = null; // cut the links between the chains
		cell1 = target_cell; // reset cell1
		cell1.parent = cell2; // cell2 is now moved up...
		cell2.branch = cell1;
		
		if (cell2.parent != null){ 
			cell2.parent.branch = cell3;
			cell2.parent = cell2.parent.parent;
			insertCell(cell2, cell2.parent.branch);
			}
		else { // it could end up being the new root
			root = cell2; 
			var extra = new BCell<A>(Math.POSITIVE_INFINITY, null, cell3, null);
			cell3.parent = extra;
			cell2.next = extra;
			} 
	}
	

	
	
	public function findMatches(item:A):List<A>{
		return new List<A>();
	}
	
	public function toString(){
		return "\n"+root.toString();
	}
	
	
}


private class BCell<A>{
	
	public var key:Null<Float>;
	public var matches:List<A>;
	public var branch:BCell<A>;
	public var next:BCell<A>;
	public var parent:BCell<A>;
	
	public function new(key:Float,item:A,?branch:BCell<A>,?next:BCell<A>, ?parent:BCell<A>){
		this.matches = new List<A>();
		this.key = key;
		this.matches.add(item);
		this.branch = branch;
		this.next = next;
		this.parent = parent;

	}
	
	public function toString(?indent:Int = 0):String{
		var s:String = "";
		for (i in 0...indent){ s+="\t";}
		s += 'key '+ key + ': ' + matches;
		if (branch != null){
			s+="\n"+branch.toString(indent+1);
		}
		if (next != null){
			s+="\n"+next.toString(indent);
		}
		return s;
	}
}






